home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group01b.txt / 000042_icon-group-sender_Thu Mar 1 17:33:52 2001.msg < prev    next >
Internet Message Format  |  2002-01-03  |  8KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.11.1/8.11.1) id f220Wso11597
  4.     for icon-group-addresses; Thu, 1 Mar 2001 17:32:54 -0700 (MST)
  5. Message-Id: <200103020032.f220Wso11597@baskerville.CS.Arizona.EDU>
  6. Date: Thu, 01 Mar 2001 15:56:45 -0500
  7. From: "Steve Graham" <Steve_Graham@labcorp.com>
  8. To: <icon-group@cs.arizona.edu>, <gep2@terabites.com>
  9. Subject: Re: New Scientist puzzle
  10. Content-Disposition: inline
  11. X-MIME-Autoconverted: from quoted-printable to 8bit by baskerville.CS.Arizona.EDU id f21L21803991
  12. Errors-To: icon-group-errors@cs.arizona.edu
  13. Status: RO
  14. Content-Length: 7176
  15.  
  16. Gordon and all,
  17.  
  18.    Based upon some comments, I've discarded the brute force approach.
  19. Here's the new code.
  20.  
  21. VIERNEUN        ;
  22.         N HI,I,LO,NEUN,SQN,SQV,VIER
  23.         S LO=1000**.5 S:LO\1'=LO LO=LO\1+1
  24.         S HI=9999**.5 S:HI\1'=HI HI=HI\1-1
  25.         F I=LO:1:HI D
  26.         . Q:$$VIER(I**2)  Q:$$NEUN(I**2)
  27.         S SQV=""
  28.         F  S SQV=$O(VIER(SQV)) Q:SQV=""  D
  29.         .  S SQN=""
  30.         .  F  S SQN=$O(NEUN(SQN)) Q:SQN=""  D
  31.         .  .  I $E(SQV,3)=$E(SQN,2),SQV'[$E(SQN),SQV'[$E(SQN,3) S VIER(SQV)=VIE"
  32.         D UNIQUE
  33.         Q
  34.         ;
  35. VIER(NUM)       ;
  36.         N A,FLGS,I S FLGS="0000000000"
  37.         F I=1:1:4 S A=$A(NUM,I)-47,$E(FLGS,A)=$E(FLGS,A)+1
  38.         I $TR($TR(FLGS,0),1)="" S VIER(NUM)="" Q 1
  39.         Q 0
  40.         ;
  41. NEUN(NUM)       ;
  42.         I $E(NUM)=$E(NUM,4),$E(NUM)'=$E(NUM,2),$E(NUM,1,2)'[$E(NUM,3) S NEUN(NU1
  43.         Q 0
  44.         ;
  45. UNIQUE  ;
  46.         N FLG,SQN,SQV
  47.         S (FLG,SQN)=""
  48.         F  S SQN=$O(NEUN(SQN)) Q:SQN=""  I NEUN(SQN)=1 D  Q:FLG
  49.         .  S SQV=""
  50.         .  F  S SQV=$O(NEUN(SQN,SQV)) Q:SQV=""  I VIER(SQV)=1 S FLG=SQV_","_SQNQ
  51.         D
  52.         . I FLG W !,$P(FLG,","),",",$P(FLG,",",2) Q
  53.         . W !,"NO ANSWERS"
  54.         Q
  55.  
  56. 6241,9409
  57.  
  58. ===
  59.  
  60. >>> <gep2@terabites.com> 02/27/01 04:36PM >>>
  61. >>> VIER and NEUN represent 4-digit squares, each letter denoting a
  62. >distinct digit. You are asked to find the value of each, given the
  63. >further requirement that each uniquely determines the other. You can
  64. >solve by looking at the squares of 32 through 99, but following my
  65. >policy of writing bad Basic in Icon I wrote boring tests to eliminate
  66. >pattern breaches.
  67.  
  68. >>> Since patterns are involved, wondered how iconians would do it at the
  69. >usual 1/5 the length and 1/20 the time. (Solution - this one's enigma
  70. >1123 -in the form sqrt(VIER * NEUN) to enigma@newscientist.com giving
  71. >your postal address.)
  72.  
  73. >>> (Horrible thought: it can't be done by *maths*, can it?)
  74.  
  75. >>Hmmmm... my program in SPITBOL finds nine solutions before the "further 
  76. >condition" is applied.  As specified, just one afterwards.
  77.  
  78. >>My final program is 8 SPITBOL statements, including the END statement.... I 
  79. >could actually reduce it to three.  :-)
  80.  
  81. >   What is the "FURTHER" condition that you mention?  I don't see how one can 
  82. uniquely determine the other.
  83.  
  84. It took me a while to figure that out, too.
  85.  
  86. If you look at your nine solutions (which are presumably the same nine that my 
  87. first program found... I didn't bother checking), you'll notice that in eight of 
  88. them, either the first square or the last square appears more than once in the 
  89. set of all solutions.   What the problem asks for is the one solution where 
  90. _both_ the first square and the last square are unique in the set of solutions.
  91.  
  92. >   I would be interested in seeing your solution.  
  93.  
  94. I'll post it at the end of this message.  It's longer in bytes than yours, (but 
  95. might not be, once your program is fixed to solve the rest of the problem!).  
  96. Mine almost certainly runs faster than yours does.  :-)
  97.  
  98. > Here is mine (with solutions) in the language I use in my daily work (Guess 
  99. what it is).  
  100.  
  101. Hmmm.... haven't a clue, but then again I've never been much of a language 
  102. wonk... despite having still used a lot of them over the years!
  103.  
  104. > I have included the square root of each solution in parentheses:
  105.  
  106. Not a bad touch, although it's easy enough to find anyhow.
  107.  
  108. >VIERNEUN        ;
  109. >        ;
  110. >        F I=1000:1:9999 D
  111. >        .I I**.5\1=(I**.5) D
  112. >        ..S X=$E(I),Y=$E(I,2),Z=$E(I,3),A=$E(I,4)
  113. >        ..I X'=Y,X'=Z,X'=A,Y'=Z,Y'=A,Z'=A D
  114. >        ...F J=1000:1:9999 D
  115. >        ....I 
  116. I'=J,J**.5\1=(J**.5),$E(I,3)=$E(J,2),$E(J)=$E(J,4),I'[$E(J),I'[$E(J,3) D
  117. >        .....W !,I," (",I**.5,"), ",J," (",J**.5,")"
  118. >
  119. >>D +1
  120. >
  121. >1369 (37), 4624 (68)
  122. >1369 (37), 5625 (75)
  123. >1764 (42), 5625 (75)
  124. >4356 (66), 1521 (39)
  125. >4761 (69), 5625 (75)
  126. >6241 (79), 9409 (97)
  127. >7056 (84), 1521 (39)
  128. >7569 (87), 1681 (41)
  129. >7569 (87), 4624 (68)
  130.  
  131. Here, as promised, is my original solution in SPITBOL:
  132.  
  133.     sq = 31
  134.     tb = table()
  135.     sqp1 = fence breakx(",") "," len(1) $ n *notany(n) $ e
  136. +       *notany(n e) $ u *n ","
  137. +     *?(sqs ? fence breakx(",") "," *notany(n e u) $ v 
  138. +       *notany(n e u v) $ i e *notany(n e u v i) $ r ","
  139. +       *?(solbuf = solbuf ";" v i e r "," n e u n) fail)
  140.     solp = fence breakx(";") ";" break(",") $ n1 "," len(4) $ n2
  141.     sup = solp *?(tb[n1] = tb[n1] + 1) *?(tb[n2] = tb[n2] + 1) fail
  142.     lp = solp *eq(tb[n1],1) *eq(tb[n2],1) *?(output = n1 "," n2) fail
  143. sqsfill    sqs = ((sqs "," (((sq = sq + 1) le(sq,99)) * sq)),
  144. +     (sqs ? sqp1), (solbuf ? sup), (solbuf ? lp))        :s(sqsfill)
  145. end
  146.  
  147. Although it's certainly true that our world of PCs today, execution times can 
  148. vary WIDELY depending on what microprocessor you're running on (I happened to 
  149. run mine on a relatively glacial, by today's standards, Pentium 233MMX), it's 
  150. still interesting perhaps to provide the output and execution statistics from my 
  151. program:
  152.  
  153. [quote]
  154.  
  155. 6241,9409
  156.  
  157. Normal end
  158. In file              play1.spt
  159. In line              13
  160. In statement         8
  161. Run time (millisec)  3
  162. Stmts executed       76
  163. MCSec / Stmt         39
  164. Regenerations        0
  165. Memory used (bytes)  83976
  166. Memory left (bytes)  47092
  167.  
  168. [end quote]
  169.  
  170. Actually, on looking at this today, I see a couple of ways to make it still 
  171. shorter and faster, which is significant enough to probably justify changing 
  172. it.... so here's the revised version (which is now down to five statements 
  173. including the END statement, and could be further reduced notationally to 
  174. three... but that change probably isn't 'worth' making):
  175.  
  176.     sq = 31
  177.     sqp1 = fence breakx("x") ("x" (len(1) $ n *notany(n) $ e
  178. +       *notany(n e) $ u *n) $ n2) $ xn2 
  179. +     *?(sqs ? fence breakx("x") ("x" (*notany(n e u) $ v 
  180. +       *notany(n e u v) $ i e *notany(n e u v i) $ r) $ n1) $ xn1
  181. +       *?(solbuf = solbuf "X" n1 xn2) 
  182. +       *?($xn1 = $xn1 + 1) *?($xn2 = $xn2 + 1) fail)
  183.     lp = fence breakx("X") ("X" len(4) $ n1) $ xn1 ("x" len(4) $ n2) $ xn2
  184. +       *eq($xn1,1) *eq($xn2,1) *?(output = n1 "," n2) fail
  185. sqsfill    sqs = ((sqs "x" (((sq = sq + 1) le(sq,99)) * sq)),
  186. +     (sqs ? sqp1), (solbuf ? lp))            :s(sqsfill)
  187. end
  188.         
  189. and the output from the last run:
  190.  
  191. [quote]
  192.  
  193. 6241,9409
  194.  
  195. Normal end
  196. In file              play3.spt
  197. In line              12
  198. In statement         5
  199. Run time (millisec)  0
  200. Stmts executed       73
  201. MCSec / Stmt         0
  202. Regenerations        0
  203. Memory used (bytes)  88440
  204. Memory left (bytes)  42628
  205.  
  206. [end quote]
  207.  
  208. Notice one huge difference between your approach and mine... mine is basically 
  209. treating the problem as a pattern matching one and does virtually everything in 
  210. character mode using the recursion and backtracking of the pattern matcher, 
  211. while yours is doing a LOT of arithmetic.      
  212.  
  213. It'll be interesting to see your program after you've handled the "uniquely 
  214. determines" condition.  I'll also be curious to see how you end up changing your 
  215. program after having looked at my solution.  :-)
  216.  
  217. Gordon Peterson                  http://personal.terabites.com/ 
  218. Support the Anti-SPAM Amendment!  Join at http://www.cauce.org/ 
  219. 12/19/98: Partisan Republicans scornfully ignore the voters they "represent".
  220. 12/09/00: the date the Republican Party took down democracy in America.
  221.  
  222.  
  223.